P5496 【模板】回文自动机(PAM)

不懂回文自动机的可以看这篇博客

现在默认大家都懂,用 Cnt[i]Cnt[i] 表示以 ii 结尾的回文串的个数。

由于 Link[i]Link[i] 表示 ii 的最长回文后缀,所以 Cnt[i]=Cnt[Link[i]]+1Cnt[i]=Cnt[Link[i]]+1(加上 ii 点所标示的一个回文串)

阅读全文 »

P3649 [APIO2014]回文串

不懂回文自动机的点这里

如果单纯的记录每个点结束回文串的数量,因为我们用的增量法 ,wwww 只会被计算一次 , 第二个样例都过不了。

所以在构建回文自动机后 , 我们将每一个 Cnt[Link[u]]+=Link[u]Cnt[Link[u]]+=Link[u] , 就可以避免由上述方法带来的影响了。

阅读全文 »

P4555 [国家集训队]最长双回文串

显然是一道回文自动机板题。

L[i]L[i] 表示以 ii 号点为左端点的最长回文串 , R[i]R[i] 表示以 ii 号点为右端点的最长回文串。

L[i]L[i] 可以通过将回文串倒过来建自动机求得 , R[i]R[i] 可以直接用原回文串建自动机求得。

阅读全文 »

CF17E Palisection

答案为所有的回文串组合-不相交的回文串组合。

cntcnt 为回文串个数 , 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求,先算出以 ii 为左端点和右端点的回文串数量 L[i]L[i] , R[i]R[i]

阅读全文 »

UVA1218 Perfect Service

一道很不错的树形dp。

dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0,表示uu为服务器,那么uu的儿子和父亲既可以是服务器,也可以不是。

阅读全文 »

CF767C Garland

首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。

记所有点权和为sumsum

容易想到,令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 , 则有转移:

阅读全文 »